//给你一个正整数 n ，生成一个包含 1 到 n² 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 3
//输出：[[1,2,3],[8,9,4],[7,6,5]]
// 
//
// 示例 2： 
//
// 
//输入：n = 1
//输出：[[1]]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 20 
// 
// Related Topics 数组 矩阵 模拟 👍 631 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

class SpiralMatrixIi {
    public static void main(String[] args) {
        Solution solution = new SpiralMatrixIi().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /*public int[][] generateMatrix(int n) {
            int[][] res = new int[n][n];
            int mid = n / 2;   // 表格中间的数字，例如:n为5，此时中心就为[2,2]
            int count = 1; // 开始遍历的数字
            int offset = 1; // 偏移量
            int loop = n / 2; // 循环的圈树，例如:n为3，此时就只需要循环1圈
            int startX = 0, startY = 0; // 开始遍历的位置

            // 以下四个循环代表遍历一圈，此时都遵循左闭右开来遍历
            while (loop > 0) {
                int i = startY, j = startX;
                // 遍历上边
                for (; j < startX + n - offset; j++) {
                    res[i][j] = count++;
                }

                // 遍历右边
                for (; i < startY + n - offset; i++) {
                    res[i][j] = count++;
                }

                // 遍历下边
                for (; j > startX; j--) {
                    res[i][j] = count++;
                }

                // 遍历左边
                for (; i > startY; i--) {
                    res[i][j] = count++;
                }

                // 将起始位置加一
                startX++;
                startY++;

                // 将循环圈数减一
                loop--;

                // 将偏移量加二，因为边界多了2条
                offset += 2;
            }

            // 如果n为奇数，将中心赋值
            if (n % 2 == 1) {
                res[mid][mid] = count;
            }

            return res;
        }*/
        // TODO 螺旋矩阵模拟
        public int[][] generateMatrix(int n) {
            int[][] array = new int[n][n];
            int top = 0, bottom = n - 1, left = 0, right = n - 1;
            int count = 1;
            while (left <= right && top <= bottom) {
                for (int column = left; column <= right; column++) {
                    array[top][column] = count++;
                }

                for (int row = top + 1; row <= bottom; row++) {
                    array[row][right] = count++;
                }

                for (int column = right - 1; column >= left + 1; column--) {
                    array[bottom][column] = count++;
                }

                for (int row = bottom; row >= top + 1; row--) {
                    array[row][left] = count++;
                }

                top++;
                bottom--;
                left++;
                right--;
            }
            return array;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
